package buaa.leetcode.DynamicPrograming;

public class UniqueBinarySearchTrees {
	public static int numTrees1(int n) {
		if(n == 0 || n == 1){
			return 1;
		}
		int[] dp = new int[n+1];
        return numTrees1(n,dp);
    }
	public static int numTrees1(int i,int[] dp){
		if(i == 0 || i == 1){
			return 1;
		}
		if(dp[i] > 0){
			return dp[i];
		}
		for(int j = 0;j<=i-1;j++){
			dp[i] += numTrees1(j,dp)*numTrees1(i-j-1,dp);
		}
		return dp[i];
	}
	public static int numTrees2(int n) {
		int[] dp = new int[n+1];
		dp[0] = dp[1] =1;
		for(int i = 2; i <=n ; i++){
			for(int j = 0;j <= i-1;j++){
				dp[i] += dp[j] * dp[i-j-1];
			}
		}
        return dp[n];
    }
	public static void main(String[] args) {
		System.out.println(numTrees2(3));
	}

}
